package com.fufu.leetcode;

/**
 * @author: BlcakTiger
 * @date: 2023/2/12 15:34
 * @contact: hsf6661@163.com
 */
public class 合并两个有序链表No21 {

    public static void main(String[] args) {
        //初始化两个链表
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(4);

        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(3);
        listNode1.next.next = new ListNode(4);
        //将两个链表合并
        ListNode merge = mergeTwoLists(listNode,listNode1);
        System.out.println(merge);
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //若其中一个链表为空，直接返回另一个链表，即便两个都为空，返回另一个也没问题，因为两个空链表合并之后还是空
        if (list1==null){
            return list2;
        }else if (list2==null){
            return list1;
        }
        //创建用于合并的新链表
        ListNode merge = new ListNode();
        //创建辅助节点，分别指向新链表、list1、list2的头节点
        ListNode h1 = list1;
        ListNode h2 = list2;
        ListNode temp = merge;

        //循环开始合并
        while (true){
            //当h1和h2都为空时，说明已经合并完成了
            if (h1==null&&h2==null){
                break;
                //其中一个为空，则直接按顺序合并另一个链表
            }else if (h1==null&&h2!=null){
                temp.next = h2;
                h2 = h2.next;
            }else if(h1!=null && h2 ==null){
                temp.next = h1;
                h1 = h1.next;
            }else {//两个都不为空时，比较二个的大小，将小的并入新链表
                if (h1.val <= h2.val) {
                    temp.next = h1;
                    h1 = h1.next;
                } else {
                    temp.next = h2;
                    h2 = h2.next;
                }
            }
            //后移准备合并下一个节点
            temp = temp.next;
        }
        //因为merge预留了一个空间，这个空间是没有元素的，所以要指向下一位
        merge = merge.next;
        return merge;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    @Override
    public String toString(){
        if (next==null){
            return val+" ";
        }
        //如果next不为空才打印
        return val+" "+next;
    }

}
